【题解】 [SDOI2010]地精部落线性DP luogu2467

好巧的一道思维题啊！

思维量极大但是码量极小，真的好巧妙啊！(好了不废话进入主题)

在下文，因为为了方便代码的理解同步，所以应用了百度翻译：

summit: 顶点

valley: 流域; 山谷，溪谷，峡谷，谷地，深谷;

这显然是道 $DP$ 题(又是废话)

可以知道题目要求的合法山脉其实是一个波动数列。

很容易的可以想到，设 $summit[i][j]$ 表示长度为 $j$ 的波动数列，此波动数列的第一个数为 $i$，且在题目中，$i$ 为山峰，这样状态下的方案总数。

同样的，我们同时设 $valley[i][j]$ 表示长度为 $j$ 的波动数列，此波动数列的第一个数为 $i$，且在题目中，$i$ 为山谷，这样状态下的方案总数。

那么答案是多少呢？由于数列中的每一个元素都可以做第一个元素，且都有可能做”山峰”或者是”山脉”，所以我们的答案应该是：

$\sum_{i=1}^{n} summit[i][n]+valley[i][n]$

现在来考虑怎么转移。

以 $summit$ 的转移为例子，假设现在需要转移 $summit[i][n]$.

那么这个波动数列的第二项肯定严格小于 $i$ ，而第三项又严格大于第二项，所以如果不看第一项的话，这个数列就变成了由第二项起头，并且第二项是”山谷”，设第二项的数为 $j$ ，那么其方案数可以用 $valley[j][n-1]$ 来表示。

由于第二项可以是数列中严格小于 $i$ 的任何数，因此我们可以列出转移式：

$summit[i][n] = \sum_{k=1}^{i-1} valley[k][n-1]$

因为题目说了是严格小于，所以可以这样子统计。

同样的，$valley[i][j]$ 也是这样转移：

$valley[i][n] = \sum_{k=i}^{n-1} summit[k][n-1]$

我们现在可以很轻易的打出正解了，但是想象一下，我们有那么大的空间吗？$2\cdot 4200\cdot 4200$？貌似很紧诶(虽然我是踩线没有 $MLE$)

那就使用滚动数组！

还有，这样子统计，复杂度将会是 $O(n^3)$ ！怎么优化呢？

前缀和就好了呀！

然后……然后就没有然后了……

Code:

#include<bits/stdc++.h>
#define ll long long
#define RI register int 
#define A printf("A")
using namespace std;
const int N=4205;
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	if(flag)x=-x;
}
int summit[N][2],valley[N][2],ans,sum,p;
int main(){
    scanf("%d%d",&sum,&p);
    summit[2][0]=1,valley[1][0]=1,valley[2][0]=1;
    for(int n=3;n<=sum;++n)
       for(int i=1;i<=n;++i){
           int sum_val,sum_sum;
           sum_val=(summit[n-1][(n-1)&1]-summit[i-1][(n-1)&1]+p)%p;
           valley[i][n&1]=(valley[i-1][n&1]+sum_val)%p;
           sum_sum=valley[i-1][(n-1)&1]%p;
           summit[i][n&1]=(summit[i-1][n&1]+sum_sum)%p;
       }
    ans=(valley[sum][sum&1]+summit[sum][sum&1])%p;
    printf("%d\n",ans);
    return 0;   
}

注意取模，不然会出锅!

本文标题:【题解】 [SDOI2010]地精部落线性DP luogu2467

文章作者:Qiuly

发布时间:2019年02月15日 - 00:00

最后更新:2019年05月07日 - 09:59

原始链接:http://qiulyblog.github.io/2019/02/15/[题解]luoguP2467/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。